// BST存在一个问题：取决于你添加的节点数，树的一条边可能会非常深；也就是说，树的一
// 条分支会有很多层，而其他的分支却只有几层

// AVL树是一种自平衡二叉搜索树，
// 意思是任何一个节点左右两侧子树的高度之差最多为1。
// 也就是说这种树会在添加或移除节点时尽量试着成为一棵完全树。

// AVL树是一种自平衡树。添加或移除节点时，AVL树会尝试自平衡。
// 任意一个节点（不论深度）的左子树和右子树高度最多相差1。
// 添加或移除节点时，AVL树会尽可能尝试转换为完全树。

// 旋转是啥玩意 看不懂 有缘再看吧

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

class SelfBalancingBinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(key) {
    const newNode = new Node(key);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) {
  }

}
